class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty()) return false;
        int m = matrix.size(), n = matrix[0].size();
        int cur_m = m - 1, cur_n = 0;
        while (cur_m >= 0 && cur_n < matrix[0].size()) {
            if (matrix[cur_m][cur_n] == target) {
                return true;
            }
            else if (matrix[cur_m][cur_n] > target){
                cur_m--;
            }
            else {
                cur_n++;
            }
        }
        return false;
    }
};
